// 请补全JavaScript代码，要求将数组参数中的数字从小到大进行排序并返回该数组。
// 注意：
// 1. 数组元素仅包含数字
// 2. 请优先使用快速排序方法
// 非原地
const _quickSort_1 = (array = []) => {
  if (array.length <= 1) return array;
  const pivot = array[0];
  const left = [];
  const right = [];
  const middle = [];
  for (const num of array) {
    if (num < pivot) left.push(num);
    else if (num > pivot) right.push(num);
    else middle.push(num);
  }
  return [..._quickSort_1(left), ...middle, ..._quickSort_1(right)];
};

// 原地算法
const quickSort_2 = function (arr = [], left = 0, right = 0) {
  if (left >= right) return;

  const midIndex = partition(arr, left, right);

  quickSort_2(arr, left, midIndex - 1);
  quickSort_2(arr, midIndex + 1, right);

  return arr;
};
function partition(arr, left, right) {
  const midVal = arr[right];

  // 小于枢轴的数下标，左移
  let slow = left - 1;
  for (let j = left; j < right; j++) {
    if (arr[j] <= midVal) {
      slow++;
      [arr[j], arr[slow]] = [arr[slow], arr[j]];
    }
  }

  // 枢轴移到正确位置
  [arr[slow + 1], arr[right]] = [arr[right], arr[slow + 1]];
  return slow + 1;
}
